// 找到个数大于一半的
// 输入：[2,2,1,1,1,2,2]
// 输出：2

function findMultiNum1 (nums) {
    const record = {
        // 2: 4,
        // 1: 3,
    };
    const count = nums.length / 2;
    for (const num of nums) {
        if (!record[num]) {
            record[num] = 1;
        } else {
            record[num]++;
        }
        if (record[num] > count) {
            return num;
        }
    }
}

var findMultiNum2 = function(nums) {

    let i = 0;
    let j = nums.length - 1;
    const temp = {
        val: null,
        count: 0,
    };

    while(i <= j) {
        if (nums[i] !== nums[j]) {
            
        } else if (!temp.count || temp.val === nums[i]) {
            temp.val = nums[i];
            temp.count += 2;
        } else {
            if (temp.count >= 2) {
                temp.count -= 2;
            } else {
                temp.val = nums[i];
            }
        }

        i ++;
        j --;
    }

    return temp.val;
};

function performance (name, cb, count = 100000) {
    console.time(name);
    for (let i = 0; i < count; i++) {
        cb();
    }
    console.timeEnd(name);
}

performance('我们', () => {
    findMultiNum1(new Array(Math.floor(Math.random() * 50)).fill(0).map(() => Math.floor(Math.random() * 8)));
});

performance('人家', () => {
    findMultiNum2(new Array(Math.floor(Math.random() * 50)).fill(0).map(() => Math.floor(Math.random() * 8)));
});

